1828F - Two Centroids - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(x) (x).begin(), (x).end()

const int N = 5e5;

int n, p[N + 1], big[N + 1], top[N + 1] = {0, 1}, tin[N + 1], tout[N + 1], tick, sm[N];
vector<int> g[N + 1];

void upd_plus(int i, int x){
	for(; i < n; i |= i + 1) sm[i] += x;
}

int get(int r){
	r++;
	int res = 0;
	for(; r; r &= r + 1) res += sm[--r];
	return res;
}

int calc(int v = 1){
	int res = 1;
	pair<int, int> mx = {0, 0};
	for(int to: g[v]){
		int temp = calc(to);
		res += temp;
		mx = max(mx, {temp, to});
	}
	big[v] = mx.second;
	vector<int> temp;
	for(int to: g[v]){
		if(to != big[v]) temp.pb(to);
	}
	g[v] = temp;
	return res;
}

void dfs(int v = 1){
	tin[v] = tick++;
	if(big[v]){
		top[big[v]] = top[v];
		dfs(big[v]);
	}
	for(int to: g[v]){
		top[to] = to;
		dfs(to);
	}
	tout[v] = tick;
}

void upd(int v){
	while(v){
		upd_plus(tin[top[v]], 1);
		upd_plus(tin[v] + 1, -1);
		v = p[top[v]];
	}
}

bool anc(int u, int v){
	return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int get_child(int u, int v){
	assert(1 <= u);
	assert(u <= n);
	if(!anc(v, u)) cout << "v = " << v << " u = " << u << endl;
	assert(anc(v, u));
	if(top[u] == top[v]) return big[v];
	u = top[u];
	if(p[u] == v) return u;
	return get_child(p[u], v);
}

void solve(){
	cin >> n;
	for(int i = 2; i <= n; i++){
		cin >> p[i];
		g[p[i]].pb(i);
	}
	calc();
	dfs();
	upd(1);
	upd(2);
	cout << "0 ";
	int c = 1, v = 2;
	for(int i = 3; i <= n; i++){
		upd(i);
		if(p[c] == v){
			if(!anc(c, i)){
				if(get(tin[c]) << 1 < i) swap(c, v);
			}
			else{
				int to = get_child(i, c);
				if(get(tin[to]) << 1 > i){
					v = c;
					c = to;
				}
				else if(get(tin[to]) > i - get(tin[c])) v = to;
			}
		}
		else{
			if(anc(v, i)){
				if(get(tin[v]) << 1 > i) swap(c, v);
			}
			else if(anc(c, i)){
				int to = get_child(i, c);
				if(get(tin[to]) << 1 > i){
					v = c;
					c = to;
				}
				else if(get(tin[to]) > get(tin[v])) v = to;
			}
			else{
				if(i > get(tin[c]) << 1){
					v = c;
					c = p[v];
				}
				else if(i - get(tin[c]) > get(tin[v])) v = p[c];
			}
		}
		if(p[c] == v) cout << (get(tin[c]) << 1) - i << ' ';
		else cout << i - (get(tin[v]) << 1) << ' ';
	}
	cout << '\n';
	tick = 0;
	for(int i = 0; i < n; i++) sm[i] = 0;
	for(int i = 1; i <= n; i++) g[i].clear();
}

main(){
	ios_base :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
}